本文提出了一项新的统计分析，旨在解释自然语言处理（NLP）中训练技术的最新成就。我们证明，当预训练任务的类（例如，蒙版语言模型任务中的不同单词）的类别足够多样化，从某种意义上说，最后一个线性层的最小奇异值在预训练中（表示为$ \ \ \ \ \ Tilde {\ nu} $）很大，然后预训练可以显着提高下游任务的样本效率。特别是，我们显示转移学习过量风险享受$ o \ left（\ frac {1} {\ tilde {\ nu} \ sqrt {n}} \ right）$ rate，与$ o \ left相比（\）标准监督学习中的frac {1} {\ sqrt {m}} \ right）$ rate。在这里，$ n $是预训练数据的数量，$ m $是下游任务中的数据数，通常是$ n \ gg m $。我们的证明依赖于矢量形式的rademacher复杂性链规则来拆卸复合函数类别和修改的自我符合条件。这些技术可能具有独立的兴趣。
translated by 谷歌翻译
将信号与噪声分开的能力以及干净的抽象对智能至关重要。有了这种能力，人类可以在不考虑所有可能的滋扰因素的情况下有效执行现实世界任务。人造代理可以做同样的事情？当噪音时，代理可以安全地丢弃什么样的信息？在这项工作中，我们根据可控性和与奖励的关系将野外信息分为四种类型，并将有用的信息归为可控和奖励相关的有用信息。该框架阐明了有关强化学习（RL）中的各种先前工作所删除的信息，并导致我们提出的学习方法，即学习一种已明确影响某些噪声分散注意器的DeNOCONE MDP。对DeepMind Control Suite和Robodesk的变体进行的广泛实验表明，我们的DeNocy World模型的表现优于仅使用原始观测值，并且超过了先前的工作，跨政策优化控制任务以及关节位置回归的非控制任务。
translated by 谷歌翻译
我们考虑光滑的凸孔concave双线性耦合的鞍点问题，$ \ min _ {\ mathbf {x}}} \ max _ {\ mathbf {y Mathbf {y}} 〜f（\ mathbf {x}} }，\ mathbf {y}） - g（\ mathbf {y}）$，其中一个人可以访问$ f $，$ g $的随机一阶oracles以及biinear耦合函数$ h $。基于标准的随机外部分析，我们提出了随机\ emph {加速梯度 - extragradient（ag-eg）}下降的算法，该算法在一般随机设置中结合了外部和Nesterov的加速度。该算法利用计划重新启动以接收一种良好的非震动收敛速率，该算法与\ citet {ibrahim202020linear}和\ citet {zhang2021lower}相匹配，并在其相应的设置中，还有一个额外的统计误差期限，以及\ citet {zhang2021lower}最多达到恒定的预取子。这是在鞍点优化中实现这种相对成熟的最佳表征的第一个结果。
translated by 谷歌翻译
本文介绍了一项有关离线增强学习中依赖间隙依赖样品复杂性的系统研究。先前的工作显示了何时最佳策略和行为策略之间的密度比上限（最佳策略覆盖范围假设），则代理可以实现$ o \ left（\ frac {1} {\ epsilon^2} \ right）$ rate，这也是最小值的最佳。我们在最佳策略覆盖范围假设下显示，当在最佳$ q $ unction中存在积极的子临时差距时，可以将费率提高到$ o \ left（\ frac {1} {\ epsilon} \ right）$。。此外，我们显示了行为策略的访问概率何时在最佳策略的访问概率为正（统一的最佳策略覆盖范围假设）的状态下，均匀下降，识别最佳政策的样本复杂性独立于$ \ frac {1} {\ epsilon} $。最后，我们呈现几乎匹配的下限，以补充我们的间隙依赖性上限。
translated by 谷歌翻译
本文为表格马尔可夫决策过程（MDP）提供了第一种多项式时间算法，该算法享受了遗憾的界限\ emph {独立于计划范围}。具体来说，我们考虑具有$ S $州的表格MDP，$ A $ ACTICY，计划范围$ h $，总奖励为$ 1 $，代理商播放$ K $ evipodes。我们设计了一种实现$ o \ left（\ mathrm {poly}（s，a，a，\ log k）\ sqrt {k} \ right）$遗憾的算法（\ mathrm {poly}（s，a，a，\ log k）polylog}（h）$依赖项〜\ citep {zhang2020 reininforcement}或对$ s $〜\ citep {li2021settling}具有指数依赖关系。我们的结果依赖于一系列新的结构引理，从而建立了固定策略的近似能力，稳定性和浓度特性，这些策略可以在与马尔可夫链有关的其他问题中应用。
translated by 谷歌翻译
无奖励强化学习（RL）考虑了代理在探索过程中无法访问奖励功能的设置，但必须提出仅在探索后才揭示的任意奖励功能的近乎最佳的政策。在表格环境中，众所周知，这是一个比奖励意识（PAC）RL（代理在探索过程中访问奖励功能）更困难的问题$ | \ Mathcal {s} | $，状态空间的大小。我们表明，在线性MDP的设置中，这种分离不存在。我们首先在$ d $二维线性MDP中开发了一种计算高效算法，其样品复杂度比例为$ \ widetilde {\ Mathcal {o}}（d^2 H^5/\ epsilon^2）$ 。然后，我们显示出$ \ omega（d^2 h^2/\ epsilon^2）$的匹配尺寸依赖性的下限，该限制为奖励感知的RL设置。据我们所知，我们的方法是第一个在线性MDP中实现最佳$ d $依赖性的计算有效算法，即使在单次奖励PAC设置中也是如此。我们的算法取决于一种新的程序，该过程有效地穿越了线性MDP，在任何给定的``特征方向''中收集样品，并在最大状态访问概率（线性MDP等效）中享受最佳缩放样品复杂性。我们表明，该探索过程也可以应用于解决线性MDP中````良好条件''''协变量的问题。
translated by 谷歌翻译
我们研究数据集假设允许求解离线双人零和Markov游戏。在与离线单代理马尔可夫决策过程的鲜明对比中，我们表明单一策略浓度假设不足以在离线双球零和马尔可夫游戏中学习纳什均衡（NE）战略。另一方面，我们提出了一个名为单侧浓度的新假设，并设计了一种悲观型算法，可在此假设下提供有效的。此外，我们表明单方面浓度假设是学习网元策略所必需的。此外，我们的算法可以实现Minimax样本复杂性，而对于两个广泛研究的设置，可以进行任何修改：数据集具有均匀浓度假设和基于转向的马尔可夫游戏。我们的工作是了解离线多智能经纪增强学习的重要初步步骤。
translated by 谷歌翻译
政策优化方法是使用最广泛使用的加固学习（RL）算法之一。然而，对这些方法的理论理解仍然不足。即使在eoisodic（时代）的表格设置中，\ citet的基于政策方法的最先进的理论结果也是只需$ \ tilde {o}（\ sqrt {s ^ 2ah ^ 4k }）$何地在$ S $是州的数量，$ a $是行动的数量，$ h $是地平线，而$ k $是剧集的数量，还有$ \ sqrt {sh} $与信息理论下限$ \ tilde {\ omega}相比，差距（\ sqrt {sah ^ 3k}）$。为了弥合这样的差距，我们提出了一种新的算法基于参考的基于参考的策略优化，在任何时间保证（\ AlgnameAcro），它具有“随时稳定”的特征。我们证明我们的算法实现$ \ tilde {o}（\ sqrt {sah ^ 3k} + \ sqrt {ah ^ 4}）$后悔。当$ s> h $时，我们的算法在忽略对数因子时最佳最佳。为了我们的最佳知识，RPO-SAT是第一次计算上高效，几乎最小的表格RL最佳策略算法。
translated by 谷歌翻译
获取一阶遗憾界限 - 遗憾的界限不是作为最坏情况，但有一些衡量给定实例的最佳政策的性能 - 是连续决策的核心问题。虽然这种界限存在于许多设置中，但它们在具有大状态空间的钢筋学习中被证明是难以捉摸的。在这项工作中，我们解决了这个差距，并表明可以将遗憾的缩放作为$ \ mathcal {o}（\ sqrt {v_1 ^ \ star}）$中的钢筋学习，即用大状态空间，即线性MDP设置。这里$ v_1 ^ \ star $是最佳政策的价值，$ k $是剧集的数量。我们证明基于最小二乘估计的现有技术不足以获得该结果，而是基于强大的Catoni平均估计器制定一种新的稳健自归一化浓度，其可能具有独立兴趣。
translated by 谷歌翻译
通过最小化同一图像的两个视图之间的距离来最大程度地减少自我监督学习的非对比度方法（例如BYOL和SIMSIAM）。这些方法在实践中取得了非凡的表现，但是理论理解落在了背后。天等。 2021解释了为什么表示形式不会崩溃到零，但是如何学习该功能仍然是神秘的。在我们的工作中，我们在线性网络中证明了非对抗性方法，学习了理想的投影矩阵，并降低了下游任务的样本复杂性。我们的分析表明，重量衰减是一个隐式阈值，它在数据增强下丢弃具有较高差异的特征，并保持差异较低的功能。受我们的理论的启发，我们通过在Tian等人的原始直接销售算法中删除特征分解步骤，从而设计了更简单，更有效的算法直接副本。 2021.我们的实验表明，直接竞争对手甚至超过了STL-10，CIFAR-10，CIFAR-100和IMAGENET的表现。
translated by 谷歌翻译